import random
import time


def partition(left, right, li):
    # 取第一个作为基准，也可以选择随机元素作为基准
    pivot = li[left]
    # 单指针
    mark = left
    for i in range(left + 1, right + 1):
        if li[i] < pivot:
            mark += 1
            # p = li[mark]
            # li[mark] = li[i]
            # li[i] = p
            li[i], li[mark] = li[mark], li[i]

    li[left] = li[mark]
    li[mark] = pivot
    return mark


def quicksort(left, right, li):
    """
    分治法
    :param left:
    :param right:
    :param li:
    :return:
    """
    if left >= right:
        return
    mid = partition(left, right, li)
    quicksort(left, mid - 1, li)
    quicksort(mid + 1, right, li)


def test():
    li = [random.randint(0, 10000) for _ in range(10000)]
    start_time = time.time()
    quicksort(0, len(li) - 1, li)
    end_time = time.time()
    print(li, '\n', end_time - start_time)


if __name__ == '__main__':
    test()
